package cc.magicjson.example.demo.collection;

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

 class Solution {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }

        return a;
    }

    public static void main(String[] args) {
        // 创建链表 A：1 -> 2 -> 3 -> 4 -> 5
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = new ListNode(5);

        // 创建链表 B：6 -> 7 -> 4 -> 5
        ListNode headB = new ListNode(6);
        headB.next = new ListNode(7);
        headB.next.next = headA.next.next.next; // 相交点 4

        Solution sol = new Solution();
        ListNode intersection = sol.getIntersectionNode(headA, headB);
        if (intersection != null) {
            System.out.println("Intersection at node with value: " + intersection.val); // 输出应该为 4
        } else {
            System.out.println("No intersection");
        }
    }
}
